Introduction to Number Theory
Topic Introduction to Number Theory. Modular arithmatic, properties of prime numbers. Seminar 17:00:00 ChanServ changed the topic of #mathematics to: SEMINAR IN PROGRESS. If you want to speak, say ! and wait to be called 17:00:25 pyninja: alright 17:00:39 pyninja: I'm going to start with the Fundamental Theorem of Arithmetic. 17:01:21 pyninja: The FTA states that all positive integers greater than 1 have a unique prime factorization. 17:03:53 pyninja: All positive integers n>1 can be uniquely represented in the form p_1^(e_1) * p_2^(e_2) * ... * p_k^(e_k), where p_i are distinct primes in increasing order and e_i are positive integers. 17:04:50 pyninja: The proof of this relies on Bezout's lemma, which is: 17:05:40 pyninja: For positive integers m,n, with d=gcd(m,n), there exist coefficients x,y such that x*m + y*n = d. 17:06:46 pyninja: Furthermore, x*m + y*n = k has integer solutions if and only if d|k. 17:07:36 pyninja: To prove this, we can let S be the set of all positive integers in the form x*m + y*n with smallest element c = a*m + b*n. 17:08:16 pyninja: Since m is in S, c <= m, so by the division algorithm, we can write m = q*c + r 17:08:31 pyninja: where q, r are integers with 0 <= r < c. 17:08:56 pyninja: We can rearrange to get r = m - q*c = m - q*(am+bn) 17:09:10 pyninja: so r = (1-qa)*m + (-b)*n. 17:09:29 pyninja: Therefore, r is either an element of S, or is 0. 17:09:46 pyninja: But since r b_i for some i. 17:22:31 pyninja: Then we can divide both sides by p_i^(b_i) to get p_1^(a_1) * ... * p_i^(a_i - b_i) * ... * p_s^(a_s) = p_1^(b_1) * ... * p_(i-1)^(b_i-1) * p_(i+1)^(b_i+1) * ... * p_t^(b_t). 17:24:02 pyninja: But now the LHS is divisible by p_i, while the RHS is not. 17:24:21 pyninja: We get the same contradiction if b_i > a_i for some i. 17:24:31 pyninja: So, a_i = b_i for all i. 17:24:57 pyninja: And we're done: all positive integers greater than 1 have a unique prime factorization. 17:25:24 pyninja: A famous consequence of this is that there are infinitely many primes. 17:26:27 pyninja: This follows when you assume the contrary and look at the number that is the product of all the primes, plus 1. 17:27:09 pyninja: There are some other proofs too, but I feel like moving to congruences now. 17:27:55 pyninja: If m|x-y, we write x=y (mod m). 17:28:11 ~astrophil: ! 17:28:17 pyninja: yes? 17:28:38 ~astrophil: Can you briefly define 'infinitely many primes'? 17:29:01 pyninja: The set of primes is infinite. 17:29:13 pyninja: There is no largest prime. 17:29:28 ~astrophil: Can we say there are 'infinite primes'? 17:30:00 _llll_: no 17:30:23 ~astrophil: Ok. 17:30:36 pyninja: :) 17:30:36 _llll_: every prime is finite. there are infinitely many of them. just like every number is finite but there are infinitely mnay of them 17:30:48 pyninja: right 17:31:18 ~astrophil: Ok, got it. 17:31:17 pyninja: Okay, so m|x-y is equivalent to x=y (mod m). 17:31:38 pyninja: This notation has some advantages in some contexts. 17:32:00 pyninja: Here, y is called a residue of x (mod m). 17:32:29 pyninja: A class of residues (mod m) consists of all numbers congruent to a given residue (mod m). 17:32:51 pyninja: For example, 2008 = 8 = -2 (mod 10). 17:33:23 pyninja: By the way, I forgot to mention that the equality sign used for congruencies has 3 bars. 17:33:45 pyninja: I'm just using = for convenience. 17:34:08 pyninja: There are 10 residue classes (mod 10), represented by 0, 1, 2, ..., 9. 17:34:28 pyninja: Some properties of congruences: 17:34:51 pyninja: Addition: a+b (mod m) = a (mod m) + b (mod m). 17:35:09 pyninja: Multiplication: ab (mod m) = (a (mod m))(b (mod m)). 17:35:39 pyninja: Division: ka = kb (mod m) <=> a=b (mod m) if, and ONLY if, gcd(k,m) = 1. 17:36:14 pyninja: Exponentiation: a^k (mod m) = (a (mod m))^k. 17:37:13 pyninja: So for example, 123456789^2 (mod 10) = 9^2 (mod 10) = (-1)^2 (mod 10). 17:37:32 pyninja: Also note that x (mod 10) is just he last digit of x. 17:37:45 pyninja: the last digit* 17:39:14 pyninja: This notation is useful for solving linear equations, for example. 17:40:00 pyninja: Consider the equation 5x + 7y = 2008. 17:40:07 pyninja: where x,y are integers. 17:40:27 pyninja: If we look at this equation (mod 5), we get: 17:40:34 pyninja: 2y = 3 (mod 5). 17:40:57 pyninja: which is equivalent to 2y = 8 (mod 5). 17:41:28 pyninja: since 2,5 are relatively prime, this means y = 4 (mod 5). 17:42:19 pyninja: That gives us an initial solution from which we can easily get the general solution. 17:43:07 pyninja: Next let's look at the totient function. 17:44:30 pyninja: The totient function is called phi(n) and is equal to the number of positive integers k <= n with gcd(k,n) = 1. 17:44:47 pyninja: (if gcd(a,b) = 1, a and b are relatively prime or coprime) 17:45:55 pyninja: So for example, phi(9) = 6 because 1, 2, 4, 5, 7 are relatively prime to 9. 17:46:03 pyninja: and also 8. 17:46:52 pyninja: It's not hard to find phi(n) once we have the prime factorization of n. 17:47:45 pyninja: In fact, phi(p_1^(e_1)*p_2^(e_2)*...*p_k^(e_k)) = n * (1-1/p1))*(1-1/p_2)*...(1-1/p_k). 17:48:20 pyninja: This function turns out to be very useful. 17:48:46 pyninja: Euler's totient theorem states that a^(phi(n)) = 1 (mod n), for all relatively prime a,n. 17:49:36 pyninja: So for example, if you wanted to find the last 2 digits of 2^2008, you need to find 2^2008 (mod 100) 17:49:59 pyninja: actually, that wouldn't work so great because 2 and 100 are not relatively prime 17:50:21 pyninja: But you can find 3^2008 (mod 100): 17:50:36 pyninja: Since phi(100) = 40, 3^40 = 1 (mod 100). 17:50:49 pyninja: So we just need to find 3^8 (mod 100). 17:51:17 pyninja: Because 3^2008 = (3^40)^50 * 3^8. 17:51:57 pyninja: It also has many other more useful / interesting applications. 17:52:53 pyninja: Let's look at some diophantine equation.s 17:53:12 pyninja: (Diophantine equations are equations in integers.) 17:55:23 pyninja: Okay, a Pythagorean triple (a,b,c) is a set of integers that satisfies the Pythagorean thoerem, a^2 + b^2 = c^2. 17:56:13 pyninja: a triple is called primitive if all three numbers are relatively prime. 17:57:17 pyninja: all primitive triples are in the from (m^2 - n^2, 2mn, m^2 + n^2). 17:57:31 pyninja: (or (2mn, m^2-n^2, m^2+n^2)) 17:58:17 pyninja: I don't think I have time to go through the whole solution, but basically you look at parity (mod 2) and (mod 4). 17:58:55 pyninja: (first of all, both a,b can't be odd) 17:59:09 pyninja: but I think I should just stop here. 17:59:36 pyninja: You can ask questions if you have any. 17:59:48 pyninja: I probably bored most people... 18:00:00 ~Bassoon: Hardly. 18:00:22 pyninja: That's good :) 18:00:49 ~Copycat: i didnt understand that phi(p_1^(e_1)*p_2^(e_2)*...*p_k^(e_k)) = n * (1-1/p1))*(1-1/p_2)*...(1-1/p_k). 18:02:46 pyninja: Well, for example, let's look at phi(10). 18:03:25 pyninja: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 18:03:50 pyninja: We have to take out the multiples of 2 and the multiples of 5. 18:04:10 ~Copycat: its 1,3,7,9 18:04:21 pyninja: Right, so phi(10) = 4. 18:04:26 ~Copycat: phi(10)=4 18:04:43 ~Copycat: and the formula? 18:04:48 pyninja: phi(2*5) = 10*(1-1/2)*(1-1/5) = 4. 18:05:16 ~Copycat: interesting but how do i proove the formula? 18:06:09 _llll_: maybe helpful to start with phi(ab)=phi(a)*phi(b) if gcd(a,b)=1 18:06:14 kommodore: Copycat: inclusion-exclusion 18:06:15 pyninja: To prove it you use the fact that phi is multiplicative 18:06:19 pyninja: yes 18:06:57 pyninja: To prove that you have to look at the residue classes. 18:09:35 ~Copycat: thanks for the seminar 18:09:45 _llll_: is there more to come next week? 18:11:04 pyninja: Sure, I'll do it if people want me to. 18:15:03 ~Bassoon: I'd be back. 18:17:39 pyninja: how about Euler's Theorem and Diophantine Equations? 18:18:38 ChanServ changed the topic of #mathematics to: NEXT SEMINAR: Euler's Theorem and Diophantine Equations by pyninja on Sunday 24 August 16:00UTC | Transcript of last seminar http://www.freenode-math.com/index.php/Introduction_to_Number_Theory | Other seminars (past and future): http://www.freenode-math.com/index.php/Seminars | You probably want to join #math until the seminar starts Category:Seminar Category:Number Theory